package com.leetcode;

import java.util.*;

/**
 * 380. O(1) 时间插入、删除和获取随机元素
 * 变长数组 + 哈希表(是真正的O(1))
 *
 * @author fy
 * @date 2022/4/13 9:43
 */
public class Solution380_2 {

    class RandomizedSet {

        private List<Integer> list;
        private Map<Integer, Integer> indices;
        private Random random;

        public RandomizedSet() {
            list = new ArrayList<>();
            indices = new HashMap<>();
            random = new Random();
        }

        public boolean insert(int val) {
            if (indices.containsKey(val)) {
                return false;
            }
            int index = list.size();
            indices.put(val, index);
            list.add(val);
            return true;
        }

        public boolean remove(int val) {
            if (!indices.containsKey(val)) {
                return false;
            }
            int index = indices.get(val);
            int lastIndex = list.size() - 1;
            // 可能要删除的项就是最后一项
            if (index != lastIndex) {
                int last = list.get(lastIndex);
                list.set(index, last);
                indices.put(last, index);
            }
            list.remove(lastIndex);
            indices.remove(val);
            return true;
        }

        public int getRandom() {
            int index = random.nextInt(list.size());
            return list.get(index);
        }
    }

}
